<?php
/**
 ***** 扶摇而上、抱守本真 ******
 * @author Dana
 * @Date 2021/7/6
 */

class TreeNode
{
    public $val = null;
    public $left = null;
    public $right = null;

    public function __construct($val = null)
    {
        $this->val = $val;
        // $this->left = $left;
        // $this->right = $right;
    }
}

class Solution
{

    protected $res = [];

    /**
     * @param TreeNode $root
     * @author Zhoufurong
     * @Date 2021/7/6
     */
    function preOrderTraversal($root)
    {
        if ($root != null) {
            $this->res[] = $root->val;
            $this->preOrderTraversal($root->left);
            $this->preOrderTraversal($root->right);
        }

        return $this->res;
    }

    // 迭代方式 后序
    function postorderTraversal($root)
    {
        // 一定要先入栈，通过子节点判断出栈
        $res = [];
        $stack = [];
        $pre = null;
        while (!empty($stack) || $root != null) {
            while ($root != null) {
                array_push($stack, $root);
                $root = $root->left;
            }

            $root = array_pop($stack);
            if ($root->right == null || $root->right == $pre) {
                $res[] = $root->val;
                $pre = $root;
                $root = null;
            } else {
                array_push($stack, $root);
                $root = $root->right;
            }
        }
        return $res;
    }

    // 迭代方式 前序
    function preTraverSal($root)
    {
        $stack = [];
        $res = [];
        array_push($stack, $root);
        while (!empty($stack)) {
            $t1 = array_pop($stack);
            $res[] = $t1->val;
            if ($t1->right != null) {
                array_push($stack, $t1->right);
            }
            if ($t1->left != null) {
                array_push($stack, $t1->left);
            }
        }

        return $res;
    }

    // 迭代方式 中序  左子树 -》根节点 -》 右子树
    function IndexTraverSal($root)
    {
        $stack = [];
        $res = [];
        if($root == null){
            return $res;
        }

        while ($root != null || !empty($stack)) {
            while ($root != null) {
                array_push($stack, $root);
                $root = $root->left;
            }
            if(!empty($stack)){
                $root = array_pop($stack);
                $res[] = $root->val;
                $root = $root->right;
            }
        }
        return $res;
    }
}

array_pad();

$node1 = new TreeNode(1);
$node2 = new TreeNode(null);
$node3 = new TreeNode(2);
$node4 = new TreeNode(3);

$node1->left = $node2;
$node1->right = $node3;
$node2->left = $node4;

$res = (new Solution())->postorderTraversal($node1);
var_dump($res);